package find

import "sort"

/**
 * @description: 74. 搜索二维矩阵
 * @keyword: 二分查找
 * @author: kami
 * @date 2023/12/10 16:00
 */
func searchMatrix(matrix [][]int, target int) bool {
	if len(matrix) == 0 || len(matrix[0]) == 0 {
		return false
	}
	m, n := len(matrix), len(matrix[0])
	i := sort.Search(m*n, func(i int) bool {
		return matrix[i/n][i%n] >= target
	})

	return i < m*n && matrix[i/n][i%n] == target
}

func searchMatrixMethod1(matrix [][]int, target int) bool {
	for i := 0; i < len(matrix); i++ {
		var left, right = 0, len(matrix[i]) - 1
		if matrix[i][left] > target {
			return false
		}
		if matrix[i][right] < target {
			continue
		}
		for left <= right {
			var mid = (left + right) / 2
			if matrix[i][mid] > target {
				right = mid - 1
			} else if matrix[i][mid] < target {
				left = mid + 1
			} else {
				return true
			}
		}
	}
	return false
}
